import java.util.*;
import java.io.*;

public class Lab3
{
	public static void main(String[] args)
	{
		new Lab3(args);
	}

	public Lab3(String[] args)
	{
		if(args.length != 1)
		{
			System.err.println("Usage `java Main FILE`");
			return;
		}

		// Initiate algorithms
		PathAlg dynamic1 = new NaiveDynamic();
		PathAlg dynamic2 = new MemoizingDynamic();
		PathAlg optimal = new ExhaustiveAlgorithm();		

		// Set up graphs
		dynamic1.buildGraph(args[0]);
		dynamic2.buildGraph(args[0]);
		optimal.buildGraph(args[0]);

		// Run algorithms and print
		dynamic1.runAlgorithmTimed();
		printAlgorithm(dynamic1);
		
		dynamic2.runAlgorithmTimed();
		printAlgorithm(dynamic2);
		
		optimal.runAlgorithmTimed();
		printAlgorithm(optimal);
	}

	private void printAlgorithm(PathAlg alg)
	{
		System.out.println("=== Running " + alg.getName() + " === ");
		System.out.print("Min. EL: "
			+ alg.getExpectedLatency() + "\nPath: ");
		for(int i : alg.getPath())
		{
			System.out.print((i+1) + " ");
		}

		System.out.println("\nExecution time in ms: " + alg.getTime());
		System.out.println();
	}

	public abstract class PathAlg {
		// Result
		protected float expectedLatency = -1;
		protected int[] path = null;
		protected long time = -1;

		// Graph
		protected float[] probabilities  = null;
		protected int[][] costs = null;

		public abstract void runAlgorithm();
		public abstract String getName();

		public long runAlgorithmTimed()
		{
			long t = Calendar.getInstance().getTimeInMillis();
			runAlgorithm();
			this.time = Calendar.getInstance().getTimeInMillis() - t;

			return this.time;
		}
		
		public void buildGraph(String inputFile)
		{
			// Parse file and set up graph
			BufferedReader in;

			try
			{
				in = new BufferedReader(new FileReader(inputFile));
			}
			catch(FileNotFoundException ex)
			{
				System.err.println("File \"" + inputFile + "\" not found.");
				return;
			}
			
			String line;
			try
			{
				int i = 0;
				int numNodes = 0;
				while((line = in.readLine()) != null)
				{
					// First line should contain our array lengths
					if(i == 0)
					{
						numNodes = Integer.parseInt(line);
						costs = new int[numNodes][numNodes];
						probabilities = new float[numNodes];

						path = new int[numNodes];
						// Always visit first node first
						this.path[0] = 0;
					}
					// The next numNodes lines should contain probabilities
					else if(i <= numNodes)
					{
						probabilities[i-1] = Float.parseFloat(line);
					}
					// And the rest should hold our cost matrix
					else
					{
						String[] nums = line.split(" ");
						for(int j=0; j<nums.length; ++j)
						{
							costs[i-1-numNodes][j] = Integer.parseInt(nums[j]);
						}
					}
					i = i + 1;
				}
			}
			catch(IOException ex)
			{
				System.err.println("Error when reading file.");
			}
		}

		public int[] getPath()
		{
			if(this.path == null)
			{
				throw new IllegalStateException("Algorithm has not been run");
			}

			return this.path;
		}

		protected float calculateExpectedLatency(int[] path)
		{
			float sum = 0;
			int pathCost = 0;
			int lastNode = 0;
			for(int v : path)
			{
				// Do not need to calculate first step 
				if(v == 0)
				{
					continue;
				}

				pathCost += costs[lastNode][v];
				sum += probabilities[v]*pathCost;

				lastNode = v;
			}

			return sum;
		}

		public float getExpectedLatency()
		{
			if(this.path == null)
			{
				throw new IllegalStateException("Algorithm has not been run");
			}

			if(this.expectedLatency < 0)
			{
				this.expectedLatency = calculateExpectedLatency(this.path);
			}

			return this.expectedLatency;
		}

		public long getTime()
		{
			if(this.time < 0)
				throw new IllegalStateException("Timed algorithm not run.");

			return this.time;
		}

		public class AlgRet {
			public float el;
			public int[] path;
			public float pp;
			public int fst;

			public AlgRet(AlgRet other)
			{
				this.el  = other.el;
				this.pp  = other.pp;
				this.fst = other.fst;

				this.path = new int[other.path.length];
				System.arraycopy(other.path, 0, this.path, 0, other.path.length);
			}

			public AlgRet(float el, int[]path)
			{
				this.el = el;
				this.path = path;
			}
			public AlgRet(int node)
			{
				this.el = 0;
				this.pp = probabilities[node];

				this.path = new int[costs.length];
				for(int i=0; i<this.path.length; ++i) {
					this.path[i] = -1;
				}

				this.fst = this.path.length - 1;
				this.path[fst] = node;
			}

			public void addNode(int node)
			{
				this.el += costs[node][this.getFst()] * this.pp;
				this.path[--fst] = node;
				this.pp += probabilities[node];
			}

			public int getFst()
			{
				return path[fst];
			}
		}
	}

	public class ExhaustiveAlgorithm extends PathAlg {
		public String getName()
		{
			return "Exhaustive";
		}

		public void runAlgorithm()
		{
			HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
			visited.put(0, true);
			AlgRet newPath = visitRest(visited, new int[] { 0 });
			this.expectedLatency = newPath.el;
			this.path = newPath.path;
		}

		private AlgRet visitRest(HashMap<Integer, Boolean> visited, int[] prePath)
		{
			AlgRet ret = null;

			for(int i=0; i<costs.length; i++) {
				if(visited.get(i) == null) {
					// The new, resulting path, after arriving at this node
					int[] pathToHere = new int[prePath.length + 1];
					// Copy previous nodes
					System.arraycopy(prePath, 0, pathToHere, 0, prePath.length);
					// Add current node last
					pathToHere[pathToHere.length - 1] = i;

					// Only leaf nodes calculate path length
					if(pathToHere.length == path.length) {
						return new AlgRet(calculateExpectedLatency(pathToHere), pathToHere);
					}
					else {
						// Mark current node as visited
						visited.put(i, true);

						// Get the shortest path from this node
						AlgRet newPath = visitRest(visited, pathToHere);

						// If this is the shortest, or the first, update return value
						if(ret == null || newPath.el < ret.el)
							ret = newPath;

						// We're leaving the node
						visited.remove(i);
					}
					
				}
			}
			return ret;
		}
	}
	
	public class NaiveDynamic extends PathAlg {
		public String getName()
		{
			return "Naive Dynamic Programming";
		}

		public void runAlgorithm()
		{
			int[] nodes = new int[costs.length];
			for(int i=0; i<costs.length; ++i) {
				nodes[i] = i;
			}

			nodes[0] = -1; // First node already visited
			AlgRet ret = opt(0, nodes);

			this.expectedLatency = ret.el;
			this.path = ret.path;
		}

		private AlgRet opt(int node, int[] nodes)
		{
			AlgRet ret = null;
			float retEL = 0;

			for(int i : nodes) {
				// If node has already been visited
				if(i == -1) {
					continue;
				}

				nodes[i] = -1; // Mark node as visited
				AlgRet tmp = opt(i, nodes);

				// If we've found a minimum
				final float tmpEL = tmp.el + costs[node][tmp.getFst()]*tmp.pp;
				if(ret == null || tmpEL < retEL ) {
					ret = tmp;
					retEL = tmpEL;
				}

				nodes[i] = i; // Leave node
			}

			// If all nodes were visited, we're at a leaf
			if(ret == null) {
				return new AlgRet(node);
			}

			// Add the current node to the return object
			ret.addNode(node);
			return ret;
		}
	}

	public class MemoizingDynamic extends PathAlg {

		// This _could_ be a list of hashmaps, but the list would then need to have
		// size equal to the sum of the weights along the longest Hamiltonian path,
		// minus the last edge. This way is also easier to program.
		private HashMap<String, List<AlgRet>> M
			= new HashMap<String, List<AlgRet>>();

		public String getName()
		{
			return "Memoizing Dynamic Programming";
		}

		public void runAlgorithm()
		{
			int[] nodes = new int[costs.length];
			for(int i=0; i<costs.length; ++i) {
				nodes[i] = i;
			}
			nodes[0] = -1; // First node already visited
			AlgRet ret = opt(0, nodes);

			this.expectedLatency = ret.el;
			this.path = ret.path;
		}

		private AlgRet opt(int node, int[] nodes)
		{
			AlgRet ret = null;
			final String hash = hash(nodes);
			List<AlgRet> candidates = M.get(hash);
			float retEL = 0;

			// If the remaining nodes already have been calculated
			if(candidates != null) {
				for(AlgRet tmp : candidates) {
					final float tmpEL = tmp.el + costs[node][tmp.getFst()]*tmp.pp;
					if(ret == null || tmpEL < retEL) {
						ret = tmp;
						retEL = tmpEL;
					}
				}

				ret = new AlgRet(ret);
			}
			else {
				candidates = new LinkedList<AlgRet>();
				for(int i : nodes) {
					// If node has already been visited
					if(i == -1) {
						continue;
					}

					nodes[i] = -1; // Mark node as visited

					AlgRet tmp = opt(i, nodes);

					// If we've found a minimum
					final float tmpEL = tmp.el + costs[node][tmp.getFst()]*tmp.pp;
					if(ret == null || tmpEL < retEL ) {
						ret = tmp;
						retEL = tmpEL;
					}

					nodes[i] = i; // Leave node
					candidates.add(new AlgRet(tmp));
				}

				// If all nodes were visited, we're at a leaf
				if(ret == null) {
					return new AlgRet(node);
				}

				// Memorize candidates
				M.put(hash, candidates);
			}

			// Add the current node to the return object
			ret.addNode(node);

			return ret;
		}

		private String hash(int[] l)
		{
			String ret = "";
			for(int i : l) {
				ret += ","+i;
			}

			return ret;
		}

	}
}

